package middle;

public class Solution_72 {
    public int minDistance(String word1, String word2) {
        char[] chars_1 = word1.toCharArray();
        char[] chars_2 = word2.toCharArray();
        int[][] arrays = new int[chars_2.length + 1][chars_1.length + 1];
        for (int i = 0; i <= chars_2.length; i++) {
            arrays[i][0] = i;
        }
        for (int i = 0; i <= chars_1.length; i++) {
            arrays[0][i] = i;
        }
        for (int i = 0; i < chars_2.length; i++) {
            for (int j = 0; j < chars_1.length; j++) {
                if (chars_2[i] == chars_1[j]) {
                    arrays[i + 1][j + 1] = arrays[i][j];
                } else {
//                    arrays[i + 1][j + 1] = Math.min(arrays[i][j], Math.min(arrays[i + 1][j], arrays[i][j + 1])) + 1;
                    arrays[i + 1][j + 1] = Math.min(arrays[i][j], arrays[i + 1][j]) + 1;
                }
            }
        }
        return arrays[chars_2.length][chars_1.length];
    }

    public static void main(String[] args) {
        Solution_72 model = new Solution_72();
        System.out.println(model.minDistance("", ""));
        System.out.println(model.minDistance("a", "ab"));
        System.out.println(model.minDistance("horse", "ros"));
        System.out.println(model.minDistance("intention", "execution"));
    }
}
